package com.sort;

import java.util.Arrays;

/**
 * 折半插入排序
 * 
 * @author zhongyi_yang
 *
 */
public class BinaryInsertSort {
	/**
	 * 折半插入排序
	 * @param dataWraps
	 */
	public static void binaryInsertSort(DataWrap[] dataWraps) {
		System.out.println("开始排序：\n");
		int arrayLength = dataWraps.length;
		for (int i = 1; i < arrayLength; i++) {
			// 当整体后移时，保证dataWraps[i]的值不会丢失
			DataWrap tmpDataWrap = dataWraps[i];
			int low = 0;
			int high = i - 1;
			while (low <= high) {
				// 找出low、high中间的索引
				int mid = (low + high) / 2;
				// 如果tmpDataWrap值大于low、high中间元素的值
				if (tmpDataWrap.compareTo(dataWraps[mid]) > 0) {
					// 限制在索引大于mid的那一半中搜索
					low = mid + 1;
				} else {
					high = mid - 1;
				}
			}
			// 将low到i处的所有元素向后整体移一位
			System.arraycopy(dataWraps, low, dataWraps, low + 1, i - low);
			// 最后将tmpDataWrap的值插入合适位置
			dataWraps[low] = tmpDataWrap;
			System.out.println(Arrays.toString(dataWraps));
		}
	}

	public static void main(String[] args) {
		DataWrap dataWrap[] = { new DataWrap(9, ""), new DataWrap(-16, ""),
				new DataWrap(21, "*"), new DataWrap(23, ""),
				new DataWrap(-30, ""), new DataWrap(-49, ""),
				new DataWrap(21, ""), new DataWrap(30, "*"),
				new DataWrap(13, "*") };
		System.out.println("排序前：" + Arrays.toString(dataWrap));
		binaryInsertSort(dataWrap);
		System.out.println("排序后：" + Arrays.toString(dataWrap));
	}
}
